package leetcode;

import java.util.HashMap;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-17 14:53
 **/
public class LeetCode560 {

    //前缀和+hash表优化
    public int subarraySum(int[] nums, int k) {
        //满足条件的个数
        int count = 0;
        //前缀和
        int pre = 0;
        HashMap< Integer, Integer > map = new HashMap <>();
        //应对有连续的多个值刚好和为k的情况
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            //如果有前缀和为pre-k的,说明就有map.get(pre-k)个满足条件的连续子数组的和为k
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            //添加前缀和pre -> 前缀和为pre个数的映射
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }


    //枚举
    /*public int subarraySum(int[] nums, int k) {
        //数组长度
        int n = nums.length;

        //满足条件的个数
        int count = 0;
        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = i; j < n; ++j) {
                sum += nums[j];
                if (sum == k) {
                    ++count;
                }
            }
        }
        return count;
    }*/



    public static void main(String[] args) {
        LeetCode560 code = new LeetCode560();
        System.out.println(code.subarraySum(new int[]{1, -1, 0}, 0));
    }

}
